import java.util.*;

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();
        for (String word : words) {
            if (!map.containsKey(word)) {
                map.put(word,1);
            }else {
                int val = map.get(word);
                map.put(word,val+1);
            }
        }
        Set<Map.Entry<String,Integer>> set = map.entrySet();
        PriorityQueue<Map.Entry<String,Integer>> queue = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (!o1.getValue().equals(o2.getValue())) {
                    return o1.getValue().compareTo(o2.getValue());
                }else {
                    return o2.getKey().compareTo(o1.getKey());
                }
            }
        });
        for (Map.Entry<String, Integer> entry : set) {
            if (queue.size() < k) {
                queue.offer(entry);
            }else {
                Map.Entry<String,Integer> top = queue.peek();
                if (top.getValue().compareTo(entry.getValue()) < 0) {
                    queue.poll();
                    queue.offer(entry);
                } else if (top.getValue().equals(entry.getValue())) {
                    if (top.getKey().compareTo(entry.getKey()) > 0) {
                        queue.poll();
                        queue.offer(entry);
                    }
                }
            }
        }
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            list.add(queue.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }
}